Introducere
Șirul lui Fibonacci este definit astfel:
Pentru a determina al n
-termen a șirului putem folosi diverse metode. Acest articol prezintă un algoritm de complexitate n
-lea termen.
Prezentul articol prezintă un algoritm de complexitate logaritmică, bazat pe înmulțirea rapidă a matricelor.
Matrice Fibonacci
Considerăm următoarea matrice:
Similar:
Observăm că
Concluzie: Dacă
Algoritm
Pentru a determina n
. Pentru a efectua repede calculele, folosim exponențierea rapidă.
Problema #Fibonacci2 cere determinarea celui de-al n
-lea termen al șirului lui Fibonacii, modulo 666013
. Succes!